Partition to K Equal Sum Subsets

LeetCode 698 | Difficulty: Medium

Medium

Problem Description

Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.

Example 1:

Input: nums = [4,3,2,3,5,2,1], k = 4
Output: true
Explanation: It is possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Example 2:

Input: nums = [1,2,3,4], k = 3
Output: false

Constraints:

- `1 <= k <= nums.length <= 16`

- `1 <= nums[i] <= 10^4`

- The frequency of each element is in the range `[1, 4]`.

Topics: Array, Dynamic Programming, Backtracking, Bit Manipulation, Memoization, Bitmask

---

Approach

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

Backtracking

Explore all candidates by building solutions incrementally. At each step, choose an option, explore further, then unchoose (backtrack) to try the next option. Prune branches that can't lead to valid solutions.

When to use

Generate all combinations/permutations, or find solutions that satisfy constraints.

Bit Manipulation

Operate directly on binary representations. Key operations: AND (&), OR (|), XOR (^), NOT (~), shifts (<<, >>). XOR is especially useful: a ^ a = 0, a ^ 0 = a.

When to use

Finding unique elements, power of 2 checks, subset generation, toggling flags.

---

Solutions

Solution 1: C# (Best: 172 ms)

Metric	Value
Runtime	172 ms
Memory	39.3 MB
Date	2021-12-13

Solution

public class Solution {
    public bool CanPartitionKSubsets(int[] nums, int k) {
        int n = nums.Length;
    int sum = nums.Sum();
    if(sum % k !=0 || n<k) return false;
    bool[] used = new bool[n];
    int target = sum/k;
        Array.Sort(nums, (a,b)=> { return b-a; });
    return KSubsetSum(nums, k, 0,0, target, used);
}

bool KSubsetSum(int[] nums, int k, int start, int curSum, int target, bool[] used)
{
    if(k==1) return true;
    if(curSum>target) return false;
    if(curSum == target) return KSubsetSum(nums, k-1,0, 0, target, used);
    
    for(int i= start;i<nums.Length;i++)
    {
        if(used[i]) continue;
        used[i] = true;
        if(KSubsetSum(nums, k, start+1, curSum+nums[i], target, used)) return true;
        used[i] = false;
    }
    
    return false;   
}
}

📜 1 more C# submission(s)

Submission (2021-12-13) — 500 ms, 39.4 MB

public class Solution {
    public bool CanPartitionKSubsets(int[] nums, int k) {
        int n = nums.Length;
    int sum = nums.Sum();
    if(sum % k !=0 || n<k) return false;
    bool[] used = new bool[n];
    int target = sum/k;
    return KSubsetSum(nums, k, 0,0, target, used);
}

bool KSubsetSum(int[] nums, int k, int start, int curSum, int target, bool[] used)
{
    if(k==1) return true;
    if(curSum>target) return false;
    if(curSum == target) return KSubsetSum(nums, k-1,0, 0, target, used);
    
    for(int i= start;i<nums.Length;i++)
    {
        if(used[i]) continue;
        used[i] = true;
        if(KSubsetSum(nums, k, start+1, curSum+nums[i], target, used)) return true;
        used[i] = false;
    }
    
    return false;   
}
}

---

Complexity Analysis

Approach	Time	Space
Dynamic Programming	$O(n)$	$O(n)$
Backtracking	$O(n! or 2^n)$	$O(n)$
Bit Manipulation	$O(n) or O(1)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.
• Identify pruning conditions early to avoid exploring invalid branches.
• LeetCode provides 1 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: We can figure out what target each subset must sum to. Then, let's recursively search, where at each call to our function, we choose which of k subsets the next value will join.